//
// Created by postgres on 5/8/17.
//
#include "../include/07graph/graph.h"
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
void CreateMGraph(MGraph *G) {
    int i, j, k, w;
    printf("%s\n", "输入顶点数和边数");
    scanf("%d,%d", &G->numVertexes, &G->numEdges);
    printf("%s\n", "读入顶点信息,建立顶点表");
    for (i = 0; i < G->numVertexes; i++) /* 读入顶点信息,建立顶点表 */
        scanf("\n%c", &G->vexs[i]);
    for (i = 0; i < G->numVertexes; i++) /* output 顶点信息,建立顶点表 */
        printf("%c", G->vexs[i]);
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j < G->numVertexes; j++)
            G->arc[i][j] = INFINITY;    /* 邻接矩阵初始化 */
    for (k = 0; k < G->numEdges; k++) /* 读入numEdges条边，建立邻接矩阵 */
    {
        printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
        scanf("%d,%d,%d", &i, &j, &w); /* 输入边(vi,vj)上的权w */
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j]; /* 因为是无向图，矩阵对称 */
    }
}

void CreateGraph2(MGraph *G) {
    G->numVertexes = 4;
    G->numEdges = 4;
    char vertexes[] = "a,b,c,d";
    char edges[] = "0,1,1,1;1,0,1,0;1,1,0,1;1,0,1,0";
    int i, j, k, w;
    char delimiters1[] = ",";
    char delimiters2[] = ";";
    /* 读入顶点信息,建立顶点表 */
    char *wrk, *rv1, *rv2;
    wrk = vertexes;
    while ((rv1 = str_split(&wrk, delimiters1))) {
        G->vexs[i] = *rv1;
        i++;
    }
    /* 邻接矩阵初始化 */
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j < G->numVertexes; j++)
            G->arc[i][j] = INFINITY;
    /* 读入numEdges条边，建立邻接矩阵 */
    wrk=edges;
    for (i = 0; i < G->numVertexes; i++) {
        rv1 = str_split(&wrk, delimiters2);
        for (j = 0; j < G->numVertexes; j++) {
            rv2 = str_split(&rv1, delimiters1);
            G->arc[i][j] = atoi(rv2);
        }
    }

}
Boolean visited[MAXVEX]; /* 访问标志的数组 */

/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G, int i)
{
    int j;
    visited[i] = TRUE;
    printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */
    for(j = 0; j < G.numVertexes; j++)
        if(G.arc[i][j] == 1 && !visited[j])
            DFS(G, j);/* 对为访问的邻接顶点递归调用 */
}

/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G)
{
    int i;
    for(i = 0; i < G.numVertexes; i++)
        visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */
    for(i = 0; i < G.numVertexes; i++)
        if(!visited[i]) /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */
            DFS(G, i);
}
void mGraph_test() {
    MGraph graph;
    CreateGraph2(&graph);
    printf("\n深度遍历：");
    DFSTraverse(graph);
}
